Cho đồ thị G (7 đỉnh) sau:

Câu hỏi: Tìm cây Steiner của W = {3,6,7} của đồ thị G.

• Ta có ma trận trọng số như sau:
  • Với dòng màu vàng là tập hợp các đỉnh.

• Ta có: V ={1,2,3,4,5,6,7} và W ={3,6,7} vậy tập S ta có là {1,2,4,5}
  • Các tập S∪W sẽ lần lượt là: W1= {3,6,7}, W2= {3,6,7,1}, W3= {3,6,7,2}, W4= {3,6,7,4}, W5= {3,6,7,5}
• Từ các tập sinh từ phép hội ta tính được trọng số nhỏ nhất thông qua thuật toán tìm cây khung nhỏ nhất lần lượt là:
  • W1: 11
  • W2: 8
  • W3: 11
  • W4: 9
  • W5: 13
• Ta chọn đồ thị sinh bởi W2 cây có độ phủ nhỏ nhất:

Tại sao đồ thị W2 có cạnh nối giữa đỉnh 1 và 3 ? Trả lời: Do không có cạnh nối giữa 1 và 3, nên:

• Cạnh (3,1) trong cây T’ sẽ được thay bằng đường đi ngắn nhất 3-4-1
• Cuối cùng ta được cây Steiner như sau:

• Các điểm Steiner: 1 và 4